<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
More Advanced Local Search Methods
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial095.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial091.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial097.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc189">13.5</A>&nbsp;&nbsp;More Advanced Local Search Methods</H2><UL>
<LI><A HREF="tutorial096.html#toc95">The Knapsack Example</A>
<LI><A HREF="tutorial096.html#toc96">Search Code Schema</A>
<LI><A HREF="tutorial096.html#toc97">Random walk</A>
<LI><A HREF="tutorial096.html#toc98">Simulated Annealing</A>
<LI><A HREF="tutorial096.html#toc99">Tabu Search</A>
</UL>

<A NAME="@default348"></A>

In the following we discuss several examples of local search
methods. These methods have originally been developed 
for unconstrained problems, but they work for certain classes of
constrained problems as well.<BR>
<BR>
The ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> code for all the examples in this section is available
in the file <TT>knapsack_ls.ecl</TT> in the <TT>doc/examples</TT> directory of your
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> installation.<BR>
<BR>
<A NAME="toc95"></A>
<H3 CLASS="subsection"><A NAME="htoc190">13.5.1</A>&nbsp;&nbsp;The Knapsack Example</H3>
<A NAME="@default349"></A>

We will demonstrate the local search methods using the well-known
knapsack problem. The problem is the following: given a container of
a given capacity and a set of items with given weights and profit
values, find out which items have to be packed into the container
such that their weights do not exceed the container's capacity and
the sum of their profits is maximal.<BR>
<BR>
The model for this problem involves N boolean variables, a single
inequality constraint to ensure the capacity restriction, and an
equality to define the objective function.<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(ic).
:- lib(repair).
knapsack(N, Profits, Weights, Capacity, Opt) :-
        length(Vars, N),
        Vars :: 0..1,
        Capacity #&gt;= Weights*Vars  r_conflict cap,
        Profit tent_is Profits*Vars,
        local_search(&lt;extra parameters&gt;, Vars, Profit, Opt).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
The parameters mean
<UL CLASS="itemize"><LI CLASS="li-itemize">
<TT>N</TT> - the number of items (integer)
<LI CLASS="li-itemize"><TT>Profits</TT> - a list of N integers (profit per item)
<LI CLASS="li-itemize"><TT>Weights</TT> - a list of N integers (weight per item)
<LI CLASS="li-itemize"><TT>Capacity</TT> - the capacity of the knapsack (integer)
<LI CLASS="li-itemize"><TT>Opt</TT> - the optimal result (output)
</UL>
<A NAME="toc96"></A>
<H3 CLASS="subsection"><A NAME="htoc191">13.5.2</A>&nbsp;&nbsp;Search Code Schema</H3>

In the literature, e.g. in [<A HREF="tutorial133.html#Localizer"><CITE>18</CITE></A>],
local search methods are often characterised by
the the following nested-loop program schema:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
local_search:
     set starting state
     while global_condition
         while local_condition
             select a move
             if acceptable
                 do the move
                 if new optimum
                     remember it
         endwhile
         set restart state
     endwhile
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>

We give three examples of local search methods coded in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> that
follow this schema: <EM>random walk</EM>, <EM>simulated annealing</EM> and
<EM>tabu search</EM>.
Random walk and tabu search do not use the full schema, as there is
only a single loop with a single termination condition.<BR>
<BR>
<A NAME="toc97"></A>
<H3 CLASS="subsection"><A NAME="htoc192">13.5.3</A>&nbsp;&nbsp;Random walk</H3>
<A NAME="@default350"></A>

The idea of Random walk is to start from a random tentative assignment of
variables to 0 (item not in knapsack) or 1 (item in knapsack), then to
remove random items (changing 1 to 0) if the knapsack's capacity is
exceeded and to add random items (changing 0 to 1) if there is
capacity left. We do a fixed number (MaxIter) of such steps and keep
track of the best solution encountered.<BR>
<BR>
Each step consists of:
<UL CLASS="itemize"><LI CLASS="li-itemize">
Changing the tentative value of some variable, which in turn causes
 the automatic recomputation of the conflict constraint set
 and the tentative objective value.
<LI CLASS="li-itemize">Checking whether the move lead to a solution and whether this
 solution is better than the best one so far.
</UL>
Here is the ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> program. We assume that the problem has been set
up as explained above. The violation of the capacity constraint
is checked by looking at the conflict constraints. If there are no
conflict constraints, the constraints are all tentatively satisfied
and the current tentative values form a solution to the problem.
The associated profit is obtained by looking at the tentative value
of the Profit variable (which is being constantly updated by <TT>tent_is</TT>).

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
random_walk(MaxIter, VarArr, Profit, Opt) :-
        init_tent_values(VarArr, random),       % starting point
        (   for(_,1,MaxIter),                   % do MaxIter steps
            fromto(0, Best, NewBest, Opt),      % track the optimum
            param(Profit,VarArr)
        do
            ( conflict_constraints(cap,[]) -&gt;   % it's a solution!
                Profit tent_get CurrentProfit,  % what is its profit?
                (
                    CurrentProfit &gt; Best        % new optimum?
                -&gt;
                    printf("Found solution with profit %w%n", [CurrentProfit]),
                    NewBest=CurrentProfit       % yes, remember it
                ;
                    NewBest=Best                % no, ignore
                ),
                change_random(VarArr, 0, 1)     % add another item
            ;
                NewBest=Best,
                change_random(VarArr, 1, 0)     % remove an item
            )
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>

The auxiliary predicate <TT>init_tent_values</TT> sets the tentative values
of all variables in the array randomly to 0 or 1:
The <TT>change_random</TT> predicate changes a randomly selected variable with
a tentative value of 0 to 1, or vice versa.
Note that we are using an array, rather than a list of variables, to
provide more convenient random access.
The complete code and the auxiliary predicate definitions can be found
in the file <TT>knapsack_ls.ecl</TT> in the <TT>doc/examples</TT> directory of your
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> installation.<BR>
<BR>
<A NAME="toc98"></A>
<H3 CLASS="subsection"><A NAME="htoc193">13.5.4</A>&nbsp;&nbsp;Simulated Annealing</H3>
<A NAME="@default351"></A>

Simulated Annealing is a slightly more complex variant of local search.
It follows the nested loop schema and uses a similar
move operator to the random walk example.
The main differences are in the termination conditions and in the
acceptance criterion for a move.
The outer loop simulates the cooling process by reducing the temperature
variable <CODE>T</CODE>, the inner loop does random moves until <CODE>MaxIter</CODE>
steps have been 
done without improvement of the objective.<BR>
<BR>
The acceptance criterion is the classical one for simulated annealing:
Uphill moves are always accepted, downhill moves with a probability
that decreases with the temperature. The search routine must be invoked
with appropriate start and end temperatures, they should roughly correspond
to the maximum and minimum profit changes that a move can incur.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
sim_anneal(Tinit, Tend, MaxIter, VarArr, Profit, Opt) :-
        starting_solution(VarArr),              % starting solution
        (   fromto(Tinit, T, Tnext, Tend),
            fromto(0, Opt1, Opt4, Opt),
            param(MaxIter,Profit,VarArr,Tend)
        do
            printf("Temperature is %d%n", [T]),
            (    fromto(MaxIter, J0, J1, 0),
                fromto(Opt1, Opt2, Opt3, Opt4),
                param(VarArr,Profit,T)
            do
                Profit tent_get PrevProfit,
                (   flip_random(VarArr),        % try a move
                    Profit tent_get CurrentProfit,
                    exp((CurrentProfit-PrevProfit)/T) &gt; frandom,
                    conflict_constraints(cap,[])   % is it a solution?
                -&gt;
                    ( CurrentProfit &gt; Opt2 -&gt;   % is it new optimum?
                        printf("Found solution with profit %w%n",
                                    [CurrentProfit]),
                        Opt3=CurrentProfit,     % accept and remember
                        J1=J0
                    ; CurrentProfit &gt; PrevProfit -&gt;
                        Opt3=Opt2, J1=J0        % accept
                    ;
                        Opt3=Opt2, J1 is J0-1   % accept
                    )
                ;
                    Opt3=Opt2, J1 is J0-1       % reject
                )
            ),
            Tnext is max(fix(0.8*T),Tend)
        ).

flip_random(VarArr) :-
        functor(VarArr, _, N),
        X is VarArr[random mod N + 1],
        X tent_get Old,
        New is 1-Old,
        X tent_set New.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
<BR>
<A NAME="toc99"></A>
<H3 CLASS="subsection"><A NAME="htoc194">13.5.5</A>&nbsp;&nbsp;Tabu Search</H3>
<A NAME="@default352"></A>
Another variant of local search is tabu search. Here, a number of moves
(usually the recent moves) are remembered (the tabu list) to direct the
search. Moves are selected by an acceptance criterion, with a 
different (generally stronger) acceptance crtierion for moves in the tabu
list. Like most local search methods there are many possible variants and
concrete instances of this basic idea. For example, how a move would be
added to or removed from the tabu list has to be specified, along with the
different acceptance criteria.<BR>
<BR>
In the following simple example, the tabu list has a length determined by
the parameter <TT>TabuSize</TT>. The local moves consist of either adding
the item with the best relative profit into the knapsack, or removing
the worst one from the knapsack. In both cases, the move gets rememebered
in the fixed-size tabu list, and the complementary move is forbidden
for the next <TT>TabuSize</TT> moves.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
tabu_search(TabuSize, MaxIter, VarArr, Profit, Opt) :-
        starting_solution(VarArr),              % starting solution
        tabu_init(TabuSize, none, Tabu0),
        (   fromto(MaxIter, I0, I1, 0),
            fromto(Tabu0, Tabu1, Tabu2, _),
            fromto(0, Opt1, Opt2, Opt),
            param(VarArr,Profit)
        do
            (   try_set_best(VarArr, MoveId),   % try uphill move
                conflict_constraints(cap,[]),   % is it a solution?
                tabu_add(MoveId, Tabu1, Tabu2)  % is it allowed?
            -&gt;
                Profit tent_get CurrentProfit,
                ( CurrentProfit &gt; Opt1 -&gt;       % is it new optimum?
                    printf("Found solution with profit %w%n", [CurrentProfit]),
                    Opt2=CurrentProfit          % accept and remember
                ;
                    Opt2=Opt1                   % accept
                ),
                I1 is I0-1
            ;
                (   try_clear_worst(VarArr, MoveId),    % try downhill move
                    tabu_add(MoveId, Tabu1, Tabu2)      % is it allowed?
                -&gt;
                    I1 is I0-1,
                    Opt2=Opt1                   % reject
                ;
                    I1=0,                       % no moves possible, stop
                    Opt2=Opt1                   % reject
                )
            )
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
<BR>
In practice, the tabu search forms only a skeleton around which a complex
search algorithm is built. An example of this is applying tabu search to
the job-shop problem, see e.g. [<A HREF="tutorial133.html#jobshoptabu"><CITE>19</CITE></A>].<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	Repair can be used to implement a wide
variety of local search and hybrid search techniques.

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 13.5: Implementing Search</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial095.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial091.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial097.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
